const removeInvalidParentheses = (s) => {
  const res = [];
  const queue = [];
  const visited = new Set();
  queue.push(s);
  while (true) {
    let len = queue.length;
    // 考虑当前层
    for (let i = 0; i < len; i++) {
      s = queue.shift();
      if (isValid(s)) {
        res.push(s);
      } else if (res.length == 0) {
        // 生成下一层，在原来的基础上再多删除一个括号
        for (let removei = 0; removei < s.length; removei++) {
          if (s[removei] == "(" || s[removei] == ")") {
            let nexts = s.substring(0, removei) + s.substring(removei + 1);
            // 防止重复
            if (!visited.has(nexts)) {
              queue.push(nexts);
              visited.add(nexts);
            }
          }
        }
      }
    }
    if (res.length > 0) {
      break;
    }
  }
  return res;
};

var isValid = function isValid(s) {
  let count = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      count++;
    } else if (s[i] === ")") {
      count--;
    }
    if (count < 0) {
      return false;
    }
  }
  return count == 0;
};
